package javazuoye.three;


import java.util.ArrayList;
import java.util.List;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/27 09:49
 */
public class _6_2_3 {
    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode(char x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode('a');
        root.left = new TreeNode('b');
        root.right = new TreeNode('c');
        root.left.left = new TreeNode('d');
        root.left.right = new TreeNode('e');
        root.right.left = new TreeNode('f');
        root.right.right = new TreeNode('g');
        TreeNode node = yes(root);
        System.out.println("层次遍历 原：");
        print(root);
        System.out.println("层次遍历 翻：");
        print(node);
    }

    public static TreeNode yes(TreeNode root) {
        TreeNode res = new TreeNode(root.val);
        if (root.right!=null){
            res.left = yes(root.right);
        }
        if (root.left!=null){
            res.right = yes(root.left);
        }
        return res;
    }

    public static void print(TreeNode root) {
        List<TreeNode> cList1 = new ArrayList<>();
        cList1.add(root);
        List<TreeNode> cList2 = new ArrayList<>();
        while (cList1.size()>0){
            for (TreeNode now : cList1) {
                System.out.print(now.val + " ");
                if (now.left != null) {
                    cList2.add(now.left);
                }
                if (now.right != null) {
                    cList2.add(now.right);
                }
            }
            System.out.println();
            cList1 = cList2;
            cList2 = new ArrayList<>();
        }
    }
}
